import java.util.Random;

public class FindKthLargest {
    public static int code(int[] nums, int k)
    {
        return qsort(nums, 0, nums.length - 1, k);
    }
    public static int qsort(int[] nums, int l, int r, int k)
    {
        if (l == r){
            return nums[l];
        }

        int left = l - 1, right = r + 1, i = l;
        int key = nums[new Random().nextInt(r - l + 1) + l];
        while (i < right){
            if (nums[i] < key){
                swap(nums, ++left, i++);
            }else if (nums[i] == key){
                i++;
            }else{
                swap(nums, --right, i);
            }
        }

        //判断在哪个区间，然后继续寻找
        int b = right - left - 1, c = r - right + 1;
        if (c >= k){
            return qsort(nums, right, r, k);
        }else if (b + c >= k){
            return key;
        }else{
            return qsort(nums, l, left ,k);
        }
    }
    public static void swap(int[] nums, int i, int j)
    {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    public static void main(String[] args) {
        System.out.println(FindKthLargest.code(new int[]{2 ,1}, 1));
    }
}
